#ifndef T_SORT_HPP
#define T_SORT_HPP

#include<vector>

class TSort {
public:
	// smallest to largest
	template<class Type>
	static void sortNoIndex(Type* dataIn, int dataNum);

	// smallest to largest
	template<class Type>
	static void sortIndexed(Type* dataIn, int dataNum, int* indexes);

	// smallest to largest
	template<class Type>
	static void sortAutoIndex(Type* dataIn, int dataNum, int* indexes);

	// same as sortNoIndex, smallest to largest
	template<class Type>
	static std::vector<int> sortSizesToIdxes(std::vector<std::vector<Type>>& vecs);

	static std::vector<int> sortSizesToIdxes(std::vector<int>& sizes);

	template<class Type>
	static std::vector<std::vector<Type>> sort(std::vector<std::vector<Type>>& vecsIn);

private:
	template<class Type>
	static int partition(int* indexes, Type* sortArray, int low, int high);

	template<class Type>
	static void sortCore(int* indexes, Type* dataIn, int low, int high);

	template<class Type>
	static int partition(Type* sortArray, int low, int high);

	template<class Type>
	static void sortCore(Type* dataIn, int low, int high);
};


// smallest to largest
template<class Type>
void TSort::sortNoIndex(Type* dataIn, int dataNum) {
	if (dataNum <= 0)
		return;
	sortCore(dataIn, 0, dataNum - 1);
}

template<class Type>
void TSort::sortIndexed(Type* dataIn, int dataNum, int* indexes) {
	if (dataNum <= 0)
		return;
	sortCore(indexes, dataIn, 0, dataNum - 1);
}

template<class Type>
void TSort::sortAutoIndex(Type* dataIn, int dataNum, int* indexes) {
	if (dataNum <= 0)
		return;
	for (int dataIdx = 0; dataIdx < dataNum; dataIdx++) {
		indexes[dataIdx] = dataIdx;
	}
	sortCore(indexes, dataIn, 0, dataNum - 1);
}

template<class Type>
std::vector<int> TSort::sortSizesToIdxes(std::vector<std::vector<Type>>& vecs) {
	if (vecs.size() == 0) {
		return std::vector<int>();
	}
	std::vector<int> sizes, indexes;
	for (std::vector<Type>& vec : vecs) {
		sizes.push_back(vec.size());
	}
	return sortSizesToIdxes(sizes);
}

template<class Type>
std::vector<std::vector<Type>> TSort::sort(std::vector<std::vector<Type>>& vecsIn) {
	std::vector<int> indexes = sortSizesToIdxes<Type>(vecsIn);
	std::vector<std::vector<Type>> vecsSorted;
	for (int idx : indexes) {
		vecsSorted.push_back(vecsIn[idx]);
	}
	return vecsSorted;
}


template<class Type>
int TSort::partition(int* indexes, Type* sortArray, int low, int high) {
	Type key = sortArray[low];
	int currentIdx = indexes[low];
	while (low < high) {
		while (low < high && sortArray[high] >= key)
			high--;
		sortArray[low] = sortArray[high];
		indexes[low] = indexes[high];

		while (low < high && sortArray[low] <= key)
			low++;
		sortArray[high] = sortArray[low];
		indexes[high] = indexes[low];
	}
	sortArray[low] = key;
	indexes[low] = currentIdx;
	return low;
};

template<class Type>
void TSort::sortCore(int* indexes, Type* dataIn, int low, int high) {
	if (low < high) {
		int result = partition(indexes, dataIn, low, high);
		sortCore(indexes, dataIn, low, result - 1);
		sortCore(indexes, dataIn, result + 1, high);
	}
}

template<class Type>
int TSort::partition(Type* sortArray, int low, int high) {
	Type key = sortArray[low];
	while (low < high) {
		while (low < high && sortArray[high] >= key)
			high--;
		sortArray[low] = sortArray[high];

		while (low < high && sortArray[low] <= key)
			low++;
		sortArray[high] = sortArray[low];
	}
	sortArray[low] = key;
	return low;
};

template<class Type>
void TSort::sortCore(Type* dataIn, int low, int high) {
	if (low < high) {
		int result = partition(dataIn, low, high);
		sortCore(dataIn, low, result - 1);
		sortCore(dataIn, result + 1, high);
	}
}
#endif